
# 和最大的子数组.超出时间限制。前缀法的思路应该没问题
def maxSubArray(self, nums: List[int]) -> int:
    if len(nums) == 1: return nums[0]
    preList = [0]  # 前缀和
    for i in range(len(nums)):
        preList.append(preList[i] + nums[i])

    ans = preList[1]

    right = len(preList) - 1
    while right >= 1:
        temp = preList[right] - min(preList[:right])
        if temp > ans:
            ans = temp
        right = right - 1
    return ans

# 前缀方法优化。在求到前i个和的时候我们只需要记录前面的和当中的最小值，这样相减我们就能找到当前位置i和为止的最小的子数组。然后我们再用一个
# 全局最小值保存最小值就可以了
def maxSubArray(self, nums: List[int]) -> int:
    if len(nums) == 1: return nums[0]
    maxSum = nums[0]
    minSum = sum = 0
    for i in range(len(nums)):
        sum = sum + nums[i] # 所有的和
        maxSum = max(maxSum, sum - minSum)
        minSum = min(minSum, sum)
    return maxSum



# 动态规划
'''
dp[i]为位置i元素所在的子数组的最大值
对于每一个元素：当前元素所在的子数组的最大值要么是自己本身，要么是把自己加入前一个子数组(i-1)。就没有其他情况了
然后我们再用一个变量存储全局的最大子数组和
'''
def maxSubArray(self, nums: List[int]) -> int:
    maxSum = curmaxSum = nums[0]
    for i in range(1, len(nums)):
        curmaxSum = max(curmaxSum + nums[i], nums[i])
        maxSum = max(maxSum, curmaxSum)
    return maxSum
